package algorithms.queue;

import java.util.Arrays;

/**
 * 基于数组的环形队列实现
 * 
 * 取模运算可以使用显式的判断数组边界来替换来改善某些情况下的性能表现
 * 
 * @author Shao
 *
 */
public class CircularQueue<T extends Comparable<T>> {

	private Object[] elemenrData;
	private final static int DEFAULT_CAPACITY = 128;
	private int capacity;

	private int head;
	// 指向末尾元素的下一个位置
	private int tail = -1;

	public CircularQueue(int capacity) {
		this.capacity = capacity;
		this.elemenrData = new Object[capacity];
	}

	public CircularQueue() {
		this.capacity = DEFAULT_CAPACITY;
		this.elemenrData = new Object[DEFAULT_CAPACITY];

	}

	public boolean isFull() {
		return tail != -1 && (tail + 1) % capacity == head;
	}

	public boolean isEmpty() {
		return tail == -1;
	}

	/**
	 * 入队操作
	 * 
	 * @param node
	 * @return
	 */
	public boolean enque(T node) {
		if (!isFull() && node != null) {
			elemenrData[tail = ((tail + 1) % capacity)] = node;
			return true;
		} else {
			return false;
		}
	}

	@SuppressWarnings("unchecked")
	public T deque() {
		T e = isEmpty() ? null : (T) elemenrData[head];
		elemenrData[head] = null;
		head = (head + 1) % capacity;
		return e;
	}

	@Override
	public String toString() {
		return "head:" + head + ",tail:" + tail + ",data:" + Arrays.asList(elemenrData).toString();
	}
}
